// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-04-06 21:44
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.TREE;

import org.junit.jupiter.api.Test;

import java.util.*;

@SuppressWarnings("ALL")

/**
 * 寻找最小高度树
 */
public class FindMinHeightTrees {
    int[] head;
    int[] to;
    int[] edge;
    int idx = 0;

    void add(int a, int b) {
        edge[idx] = head[a];
        to[idx] = b;
        head[a] = idx++;
    }

    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        // 使用BFS遍历树的每一个节点，并且记录当前节点的高度，高度最小的进入结果列表返回
        // 链式
        List<Integer> ans = new ArrayList<>();
        Queue<Integer> queue = new ArrayDeque<>();
        head = new int[n + 1];
        to = new int[n * 4];
        edge = new int[4 * n];
        Arrays.fill(edge, -1);
        Arrays.fill(head, -1);
        Arrays.fill(to, -1);
        int[] len = new int[n];
        int min = Integer.MAX_VALUE;
        for (int[] e : edges) {
            add(e[0], e[1]);
            add(e[1], e[0]);
        }
        for (int i = 0; i < n; i++) {
            boolean[] visited = new boolean[n];
            int layer = 1, nLayer = 0, height = 0;
            queue.offer(i);
            while (!queue.isEmpty()) {
                int root = queue.poll();
                visited[root] = true;
                layer--;
                for (int j = head[root]; j != -1; j = edge[j]) {
                    if (!visited[to[j]]) {
                        queue.offer(to[j]);
                        nLayer++;
                    }
                }
                if (layer == 0) {
                    height++;
                    layer = nLayer;
                    nLayer = 0;
                }
            }
            len[i] = height;
            min = Math.min(len[i], min);
        }
        for (int i = 0; i < n; i++) {
            if (len[i] == min) {
                ans.add(i);
            }
        }
        return ans;
    }


    @Test
    public void shout() {
        int n = 4;
        int[][] edges = {{1, 0}, {1, 2}, {1, 3}};
        System.out.println(findMinHeightTrees(n, edges));
    }
}
